
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution
{
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        ListNode *root = new ListNode;
        int top = 0;
        ListNode *cur = root;
        while (l1 || l2)
        {
            int sum = top;
            if (l1)
                sum += l1->val, l1 = l1->next;
            if (l2)
                sum += l2->val, l2 = l2->next;
            top = sum / 10;
            auto newNode = new ListNode(sum % 10);
            cur->next = newNode;
            cur = newNode;
        }
        if (top != 0)
        {
            auto newNode = new ListNode(top);
            cur->next = newNode;
        }
        ListNode *ret = root->next;
        delete root;
        return ret;
    }
};